package com.Offer;

/*
    面试题44：数字序列中某一位的数字
    数字以0123456789101112131415..的格式序列化到一个字符序列中。
    在这个序列中，第5位(从0开始)是5，第13是1，第19是4，等等。
    请写一个函数，求任意第n位对应的数字
 */
public class demo44 {
    public static void main(String[] args) {
        System.out.println(digitAtIndex(10));

    }

    public static int digitAtIndex(int index){
        if(index < 0)
            return -1;
        int digits = 1;
        while(true){
            int number = countOfIntegers(digits);
            if(index < number * digits)
                return digitAtIndex(index,digits);
            index -= digits*number;
            digits++;
        }
    }


    //m位的数字的总个数，比如输入2，范围10~99共90个数；输入3，返回100~999的个数900
    public static int countOfIntegers(int digits){
        if (digits == 1)
            return 10;
        return 9*(int)Math.pow(10,digits-1);
    }

    //获得m位数中的那个数字
    public static int digitAtIndex(int index,int digits){
        int number = beginNumber(digits) + index/digits;    //获得序列化的某个数number
        int indexFromRight = digits - index % digits;   //得到要index在number中需要从右边删除的个数，比如811 = 270*3+1，indexFromRight = 2，代表我们要找的是在从右往左数第二个数
        for (int i = 1; i < indexFromRight; ++i) {
            number /= 10;
        }
        return number % 10;
    }

    //得到第一个m位数是什么，比如2位数的第一个数是10，3位数是100
    public static int beginNumber(int digits){
        if(digits == 1)
            return 0;
        return (int)Math.pow(10,digits-1);
    }
}

